package class03;

import java.util.Arrays;

/**
 * @description: 二分法
 * @time: 2021/7/6 12:40
 * @author: lhy
 */
public class BinarySearch {
    /**
     * 经典的二分法
     * @param arr sortedArray
     * @param value findNumber
     * @return index
     */
    public static int binarySearch(int[] arr, int value){
        int l = 0;
        int r = arr.length - 1;
        if (arr == null || r == -1){
            return -1;
        }
        while (l <= r){
            // 防溢出
            int mid = l + (r - l) / 2;
            if(arr[mid] == value){
                return mid;
            }else if (arr[mid] < value){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return -1;
    }
    
    /**
     * 暴力求解
     */
    public static int test(int[] sortedArray, int value){
        for (int i = 0; i < sortedArray.length; i++) {
            if (value == sortedArray[i]) {
                return i;
            }
        }
        return -1;
    }


    public static int[] generateRandomArray(int maxLen, int maxValue){
        // len ∈ [1,maxLen]
        int len = (int) (Math.random() * maxLen ) + 1;
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            // value ∈ [-maxValue,maxValue]
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue+1) * Math.random());
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTimes = 100000;
        int maxLen = 10000;
        int maxValue = 10000;
        boolean flag = true;

        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxLen,maxValue);
            Arrays.sort(arr);
            int value = arr[(int) (Math.random() * arr.length)];
            int indexB = binarySearch(arr,value);
            int indexT = test(arr,value);
            if (arr[indexB] != arr[indexT]){
                flag = false;
                System.out.println("Array: " + Arrays.toString(arr));
                System.out.println("value: " + value);
                System.out.println("Index: " + indexB);
                break;
            }
        }
        System.out.println(flag ? "Succeed!" : "Fucking fucked!");
    }
}
